package 链表;

/**
 * @Author zxl
 * @Date 2021/12/25 21:16
 * @Desc
 */
public class 分隔链表 {

    /**
     * 初始化链表
     *
     * @return
     */
    public static Node initData() {
        Node node1 = new Node();
        node1.value = 1;
        Node node2 = new Node();
        node2.value = 4;
        Node node3 = new Node();
        node3.value = 3;
        Node node4 = new Node();
        node4.value = 2;
        Node node5 = new Node();
        node5.value = 5;
        Node node6 = new Node();
        node6.value = 2;


        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;

        return node1;
    }

    /**
     * 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前
     * 你不需要 保留 每个分区中各节点的初始相对位置。
     *
     * @param args
     */
    public static void main(String[] args) {

        int value = 3;
        Node head = initData();
        System.out.println("数字：" + value + ",分隔前链表:" + head);
        Node res = divide3(head, value);
        System.out.println("分隔后：" + res);

    }


    public static Node divide3(Node head, int num) {

        Node minHead = new Node(), maxHead = new Node();
        Node minHeadTemp = minHead, maxHeadTemp = maxHead;
        while (head != null) {
            if (head.value < num) {
                minHead.next = head;
                minHead = minHead.next;
                ;
            } else {
                maxHead.next = head;
                maxHead = maxHead.next;
            }
            head = head.next;
        }
        minHead.next = maxHeadTemp.next;
        maxHead.next = null;
        return minHeadTemp.next;
    }


    public static Node divide2(Node head, int value) {
        Node node1 = new Node();
        Node head1 = node1;
        Node node2 = new Node();
        Node head2 = node2;
        while (head != null) {
            if (head.value < value) {
                node1.next = head;
                node1 = node1.next;
            } else {
                node2.next = head;
                node2 = node2.next;
            }
            head = head.next;
        }
        node1.next = null;
        node2.next = null;
        node1.next = head2.next;
        return head1.next;

    }


    /**
     * 分隔链表
     *
     * @param head  头节点
     * @param value 分隔值
     * @return
     */
    public static Node divide(Node head, int value) {
        if (head == null || head.next == null) {
            return head;
        }
        Node maxLinkHead = new Node();
        Node newMaxHead = maxLinkHead;
        Node minLinkHead = new Node();
        Node newMinHead = minLinkHead;
        while (head != null) {
            if (head.value < value) {
                minLinkHead.next = head;
                minLinkHead = minLinkHead.next;
                head = head.next;
            } else {
                maxLinkHead.next = head;
                maxLinkHead = maxLinkHead.next;
                head = head.next;
            }
        }
        minLinkHead.next = newMaxHead.next;
        maxLinkHead.next = null;
        return newMinHead.next;

    }
}
